home *** CD-ROM | disk | FTP | other *** search
/ Acorn User: China / Acorn User China CD-ROM (UK) (Disc A) / Acorn User China CD-ROM (UK) (Disc A).bin / ARMCLUB / DRUCK / SPRITE_TOOLS.ARC / c / palette < prev    next >
Encoding:
Text File  |  1998-04-03  |  19.5 KB  |  658 lines
  1. /************************************************************************
  2.  *                                                                      *
  3.  * palette.c                                                            *
  4.  * =========                                                            *
  5.  *                                                                      *
  6.  * Palette optimization function library                                *
  7.  * Uses spr_info generic bitmap interface from sprite.c library         *
  8.  *                                                                      *
  9.  * Version 0.35 (05-May-1993)                                           *
  10.  *                                                                      *
  11.  * (C) 1993 DEEJ Technology PLC                                         *
  12.  *                                                                      *
  13.  ************************************************************************/
  14.  
  15. #include <stdlib.h>
  16. #include <stdio.h>
  17. #include <string.h>
  18. #include "io.h"
  19. #include "sprite.h"
  20. #include "process.h"
  21. #include "palette.h"
  22.  
  23. /* Global data with in libarary */
  24.  
  25. static opt_table_entry **table;
  26. static int             table_size;
  27.  
  28. /* library internal function prototypes */
  29.  
  30. static void closest_entry(int);
  31. static void make_closests(void);
  32. static int find_closest(void);
  33. static void eliminate(int);
  34. static void update_closests(int);
  35. static int calc_filter(hist_info*, int);
  36. static void filter_histogram(hist_info*, int);
  37.  
  38.  
  39. /****************************************************************************/
  40.  
  41. /*
  42.  * finds the closed and second closest entries
  43.  * in the colour optimization table to the given entry,
  44.  * and fills in the closest & diff fields
  45.  */
  46.  
  47. static void closest_entry(int index)
  48. {
  49. #ifdef SQR_TABLE
  50.         static int     squares[1024];
  51. #endif
  52.         REGISTER int i;
  53.         REGISTER int r, g, b, r2, g2, b2;
  54.         REGISTER int rd, gd, bd;
  55.     REGISTER int diff;
  56.              int close_diff[2];
  57.                  int closest[2];
  58.  
  59. #ifdef SQR_TABLE
  60.         if(squares[2] != 4)
  61.         {
  62.                 for(i=-512; i<512; i++)
  63.                 {
  64.                         squares[512+i] = i*i;
  65.                 }
  66.         }
  67. #endif
  68.  
  69.         close_diff[0] = MAX_DIFF;
  70.         close_diff[1] = MAX_DIFF;
  71.  
  72.         r = (table[index]->value >>  8) & 0xFF;
  73.         g = (table[index]->value >> 16) & 0xFF;
  74.         b = (table[index]->value >> 24) & 0xFF;
  75.  
  76.         for(i=0; i<table_size; i++)
  77.         {
  78.                 /* prevent match with itself, or deleted entry */
  79.  
  80.                 if(i!=index && table[i]!=0)
  81.                 {
  82.                         r2 = (table[i]->value >>  8) & 0xFF;
  83.                         g2 = (table[i]->value >> 16) & 0xFF;
  84.                         b2 = (table[i]->value >> 24) & 0xFF;
  85.  
  86.                         /* difference calculation */
  87.  
  88.                         rd = r - r2;
  89.                         gd = g - g2;
  90.                         bd = b - b2;
  91.  
  92. #ifdef SQR_TABLE
  93.                         diff = squares[512+rd] * 3 +
  94.                                squares[512+gd] * 6 +
  95.                                squares[512+bd]; 
  96. #else
  97.                         diff = rd*rd * 3 +
  98.                                gd*gd * 6 +
  99.                                bd*bd; 
  100. #endif
  101.  
  102.                         /* check for better matches */
  103.  
  104.                         if(diff < close_diff[0])
  105.                         {
  106.                                 close_diff[1] = close_diff[0];
  107.                                 close_diff[0] = diff;
  108.                                 closest[1]    = closest[0];
  109.                                 closest[0]    = i;
  110.                         }
  111.                         else
  112.                         {
  113.                             if(diff < close_diff[1])
  114.                             {
  115.                                 close_diff[1] = diff;
  116.                                 closest[1]    = i;
  117.                             }
  118.                         }
  119.                 }
  120.         }
  121.  
  122.         /* fill out table entry fields */
  123.  
  124.         table[index]->closest[0] = closest[0];
  125.         table[index]->closest[1] = closest[1];
  126.         table[index]->diff[0]    = close_diff[0];
  127.         table[index]->diff[1]    = close_diff[1];
  128. }
  129.  
  130. /*
  131.  * for each colour in the table finds the closest
  132.  * colour to it in the rest of the table
  133.  *
  134.  * Also ensure that the colours closest to the 8
  135.  * colours at the corner of the colour cubes are
  136.  * fixed by setting bit 0 of their value to 1  
  137.  */
  138.  
  139. static void make_closests(void)
  140. {
  141.         int i;
  142.     int closest;
  143.  
  144.         progress_start("Differencing:");
  145.  
  146.         for(i=0; i<table_size; i++)
  147.         {
  148.                 if(table[i] != 0)
  149.                         closest_entry(i);
  150.  
  151.                 progress(i, table_size);
  152.         }
  153.         progress_finish();
  154.  
  155.     /*
  156.          * uses extra entry in table to find closests
  157.          * to coreners of rgb colour cube
  158.          */
  159.  
  160.         if((table[table_size]=
  161.             (opt_table_entry*)malloc(sizeof(opt_table_entry))) ==0)
  162.         {
  163.             fprintf(stderr,"Unable to allocate optimization table entry\n");
  164.                 exit(1);
  165.         }
  166.  
  167.     for(i=0; i<8; i++)
  168.     {
  169.         switch(i)
  170.         {
  171.             case 0:    table[table_size]->value = 0x00000000; break;
  172.             case 1:    table[table_size]->value = 0x0000FF00; break;
  173.             case 2:    table[table_size]->value = 0x00FF0000; break;
  174.             case 3:    table[table_size]->value = 0x00FFFF00; break;
  175.             case 4:    table[table_size]->value = 0xFF000000; break;
  176.             case 5:    table[table_size]->value = 0xFF00FF00; break;
  177.             case 6:    table[table_size]->value = 0xFFFF0000; break;
  178.             case 7:    table[table_size]->value = 0xFFFFFF00; break;
  179.         }
  180.         /* find closests to corner value */
  181.  
  182.         closest_entry(table_size);
  183.  
  184.         /* fix the cloesest entry */
  185.  
  186.         closest                = table[table_size]->closest[0];
  187.         table[closest]->value |= 1;
  188.     }
  189.  
  190.     free((void*)table[table_size]);
  191.     table[table_size] = 0;
  192. }
  193.  
  194. /*
  195.  * Updates the closest relationships in the table
  196.  * after removing the target colour
  197.  */
  198.  
  199. static void update_closests(int target)
  200. {
  201.         int i;
  202.  
  203.         for(i=0; i<table_size; i++)
  204.         {
  205.                 if(table[i] != 0)
  206.                 {
  207.                         if(table[i]->closest[0] == target  ||
  208.                            table[i]->closest[1] == target) 
  209.                         {
  210.                                 closest_entry(i);
  211.                         }
  212.                 }
  213.         }
  214. }
  215.  
  216. /*
  217.  * Find entry that has the smallest weighted difference
  218.  * between its two closest entries in the table.
  219.  * Weighting is determied by RGB least squares difference and
  220.  * the colour use count 
  221.  */
  222.  
  223. static int find_closest(void)
  224. {
  225.         int   i;
  226.         float d1, d2;
  227.         float diff;
  228.         int   target;
  229.         float closest_diff = (float)MAX_DIFF;
  230.  
  231.         for(i=0; i<table_size; i++)
  232.         {
  233.         /* check for empty or fixed entry */
  234.  
  235.                 if((table[i]!=0) && ((table[i]->value & 1)==0))
  236.                 {
  237.                         d1     = (float)table[i]->diff[0];
  238.                         d2     = (float)table[i]->diff[1];
  239.  
  240.                         diff = ((float)table[i]->count*d1*d2) / (d1+d2);
  241.  
  242.                         if(diff<closest_diff && diff>0)
  243.                         {
  244.                                 closest_diff = diff;
  245.                                 target       = i;
  246.                         }
  247.                 }
  248.         }
  249.         return(target);
  250. }
  251.  
  252. /*
  253.  * Eliminate a colour from the table and distribute
  254.  * its usage between its two closest alternate colours
  255.  */
  256.  
  257. static void eliminate(int target)
  258. {
  259.         int close1 = table[target]->closest[0];
  260.         int close2 = table[target]->closest[1];
  261.         int diff1  = table[target]->diff[0];
  262.         int diff2  = table[target]->diff[1];
  263.  
  264.         table[close1]->count += ((table[target]->count * diff2) /
  265.                                  (diff1 + diff2));
  266.  
  267.         table[close2]->count += ((table[target]->count * diff1) /
  268.                                  (diff1 + diff2));
  269.  
  270.         /* remove target colour's entry */
  271.  
  272.         free((void*)table[target]);
  273.         table[target] = 0;
  274. }
  275.  
  276.  
  277. /*
  278.  * Calculate the optimium palette for an image
  279.  */
  280.  
  281. hist_info *build_histogram(spr_info_str *in)
  282. {
  283.         static hist_info h;
  284.         hist_entry  **hash_table;
  285.         hist_entry  *entry_ptr, *last_ptr;
  286.         int         i, x, y ;
  287.         uint        rgb, r, g, b;
  288.         int         hash_val;
  289.  
  290.         if((hash_table = (hist_entry**)malloc(HASH_SIZE *
  291.                                                sizeof(hist_entry_ptr)))==0)
  292.         {
  293.                 fprintf(stderr,"Unable to allocate hash table\n");
  294.                 exit(1);
  295.         }
  296.  
  297.         for(i=0; i<HASH_SIZE; i++)
  298.                 hash_table[i] = 0;
  299.  
  300.         h.colours    = 0;
  301.         h.hash_hits  = 0;
  302.         h.hash_miss  = 0;
  303.         h.hash_used  = 0;
  304.         h.hash_chain = 0;
  305.  
  306.         /*
  307.          * find and count all used colours in image
  308.          */
  309.  
  310.         progress_start("Histograming:");
  311.  
  312.         for(y=0; y<in->Y; y++)
  313.         {
  314.             for(x=0; x<in->X; x++)
  315.             {
  316.                 rgb = in->read_pixel_rgb(in, x, y);
  317.  
  318.                 r = (rgb >>  8) & 0xFF;
  319.                 g = (rgb >> 16) & 0xFF;
  320.                 b = (rgb >> 24) & 0xFF;
  321.  
  322.                 hash_val = HASH_ALG(r,g,b);
  323.  
  324.                 /* make hash entry if location is empty */
  325.  
  326.                 if(hash_table[hash_val] == 0)
  327.                 {
  328.                         if((hash_table[hash_val] =
  329.                                 (hist_entry*)malloc(sizeof(hist_entry))) == 0)
  330.                         {
  331.                                 fprintf(stderr,
  332.                                         "Hash table out of memory\n");
  333.                                 exit(1);
  334.                         }
  335.                         hash_table[hash_val]->next  = 0;
  336.                         hash_table[hash_val]->value = rgb;
  337.                         hash_table[hash_val]->count = 0;
  338.  
  339.                         h.hash_used++;
  340.                         h.colours++;
  341.                 }
  342.                 entry_ptr = hash_table[hash_val];
  343.  
  344.                 /* check for match at hash table level */
  345.  
  346.                 if(entry_ptr->value == rgb)
  347.                 {
  348.                         /* increment usage count */
  349.  
  350.                         entry_ptr->count++;
  351.                         h.hash_hits++;
  352.                 }
  353.                 else
  354.                 {
  355.                         /* check for match along chain from table */
  356.  
  357.                         BOOL found=FALSE;
  358.  
  359.                         h.hash_miss++;
  360.  
  361.                         i = 1;
  362.  
  363.                         last_ptr  = entry_ptr;
  364.                         entry_ptr = entry_ptr->next;
  365.  
  366.                         while(entry_ptr!=0 && found==FALSE)
  367.                         {
  368.                                 if(entry_ptr->value == rgb)
  369.                                 {
  370.                                         found = TRUE;
  371.                                 }
  372.                                 else
  373.                                 {
  374.                                         last_ptr  = entry_ptr;
  375.                                         entry_ptr = entry_ptr->next;
  376.                                         i++;
  377.                                 }
  378.                         }
  379.  
  380.                         /* make new entry at end of chain */
  381.  
  382.                         if(found == FALSE)
  383.                         {
  384.                                 if((entry_ptr = (hist_entry*)
  385.                                     malloc(sizeof(hist_entry))) == 0)
  386.                                 {
  387.                                         fprintf(stderr,
  388.                                                 "Hash entries out of memory\n");
  389.                                         exit(1);
  390.                                 }
  391.                                 last_ptr->next   = entry_ptr;
  392.                                 entry_ptr->next  = 0;
  393.                                 entry_ptr->value = rgb;
  394.                                 entry_ptr->count = 0;
  395.  
  396.                                 if(i > h.hash_chain) h.hash_chain = i;
  397.                                 h.colours++;
  398.                         }
  399.                         /* increment usage count */
  400.  
  401.                         entry_ptr->count++;
  402.                 }
  403.             }
  404.             progress(y, in->Y);
  405.         }
  406.  
  407.         /*
  408.          * scan colour use table to determine filter values
  409.          */
  410.  
  411.         i           = 0;
  412.         h.more1     = 0;
  413.         h.more10    = 0;
  414.         h.more100   = 0;
  415.         h.more_frac = 0;
  416.         h.fraction  = (in->X * in->Y)/FILTER_FRAC;
  417.         h.max_use   = 0;
  418.         h.avg_use   = 0;
  419.         last_ptr    = 0;
  420.  
  421.         for(hash_val=0; hash_val<HASH_SIZE; hash_val++)
  422.         {
  423.                 entry_ptr = hash_table[hash_val];
  424.  
  425.                 /* fix hash table/chains to make full linked list */
  426.  
  427.                 if(last_ptr!=0 && entry_ptr!=0)
  428.                 {
  429.                         last_ptr->next = entry_ptr;
  430.                 }
  431.  
  432.                 while(entry_ptr != 0)
  433.                 {
  434.                         i++;
  435.  
  436.                         if(entry_ptr->count >          1) h.more1++;
  437.                         if(entry_ptr->count >         10) h.more10++;
  438.                         if(entry_ptr->count >        100) h.more100++;
  439.                         if(entry_ptr->count > h.fraction) h.more_frac++;
  440.                         if(entry_ptr->count >  h.max_use) h.max_use =
  441.                                                           entry_ptr->count;
  442.                         h.avg_use += entry_ptr->count;
  443.  
  444.                         last_ptr  = entry_ptr;
  445.                         entry_ptr = entry_ptr->next;
  446.                 }
  447.         }
  448.  
  449.         h.avg_use /= h.colours;
  450.  
  451.         /*
  452.          * can delete hash table as entries are now linked list
  453.          * but find head of list first
  454.          */
  455.  
  456.         i = 0;
  457.         while(hash_table[i] == 0)
  458.         {
  459.                 i++;
  460.         }
  461.         
  462.         h.list_head = hash_table[i];
  463.  
  464.         free((void*)hash_table);
  465.  
  466.         progress_finish();
  467.  
  468.         return(&h);
  469. }
  470.  
  471. /*
  472.  * Calculate colour use filter threshold aim to
  473.  * reduce table to < TABLE_MAX entries but greater
  474.  * than the destination palette size. Can be larger
  475.  * than TBALE_MAX so as to keep all colours used
  476.  * more than FILTER_FRAC of total image area
  477.  */
  478.  
  479. static int calc_filter(hist_info *h, int min_cols)
  480. {
  481.         int         filter;
  482.  
  483.         filter     = h->fraction;
  484.         table_size = h->more_frac;
  485.  
  486.         if(table_size<TABLE_MAX && h->more100>table_size && h->more100<TABLE_MAX)
  487.         {
  488.                 filter     = 100;
  489.                 table_size = h->more100;
  490.         }
  491.         if(table_size<TABLE_MAX && h->more10>table_size && h->more10<TABLE_MAX)
  492.         {
  493.                 filter     = 10;
  494.                 table_size = h->more10;
  495.         }
  496.         if(table_size<TABLE_MAX && h->more1>table_size && h->more1<TABLE_MAX)
  497.         {
  498.                 filter     = 1;
  499.                 table_size = h->more1;
  500.         }
  501.         if(table_size<TABLE_MAX && h->colours<TABLE_MAX)
  502.         {
  503.                 filter     = 0;
  504.                 table_size = h->colours;
  505.         }
  506.                 
  507.         return(filter);
  508. }
  509.  
  510. /*
  511.  * Make optimization table by filtering hash_table
  512.  * hash_table list entries can be removed after copying
  513.  * 'table' and 'table_size' are globals
  514.  */
  515.  
  516. static void filter_histogram(hist_info *h, int filter)
  517. {
  518.         hist_entry *entry_ptr;
  519.         hist_entry *last_ptr;
  520.         int         i;
  521.  
  522.     /* allocate table size + 1 for temporary calculations */
  523.  
  524.         if((table = (opt_table_entry **)malloc((table_size+1) *
  525.                                                sizeof(opt_table_entry_ptr)))==0)
  526.         {
  527.                 fprintf(stderr,"Unable to allocate optimization table\n");
  528.                 exit(1);
  529.         }
  530.  
  531.         i         = 0;
  532.         entry_ptr = h->list_head;
  533.  
  534.         while(entry_ptr != 0)
  535.         {
  536.                 if(entry_ptr->count > filter)
  537.                 {
  538.                         if((table[i]=(opt_table_entry*)malloc(
  539.                                                 sizeof(opt_table_entry))) ==0)
  540.                         {
  541.                                 fprintf(stderr,"Unable to allocate optimization table entry\n");
  542.                                 exit(1);
  543.                         }
  544.                         table[i]->value      = entry_ptr->value;
  545.                         table[i]->count      = entry_ptr->count;
  546.                         table[i]->closest[0] = 0;
  547.                         table[i]->closest[1] = 0;
  548.                         table[i]->diff[0]    = MAX_DIFF;
  549.                         table[i]->diff[1]    = MAX_DIFF;
  550.                         i++;
  551.                 }
  552.                 last_ptr  = entry_ptr;
  553.                 entry_ptr = entry_ptr->next;
  554.                 free((void*)last_ptr);
  555.         }
  556. }
  557.  
  558. /*
  559.  * Calculate the optimium palette for an image
  560.  *
  561.  * If source image has more colours than destination
  562.  * colours are calculated on a use/RGB difference alogorithm
  563.  * to produce the smallest error in the output image.
  564.  * If the destination has more colurs than the source, its
  565.  * palette is set to contain only the colours used in the
  566.  * source image, rather than its whole palette.
  567.  * The output palette must have more than 8 colours.
  568.  */
  569.  
  570. void optimize_palette(spr_info_str *in, spr_info_str *out)
  571. {
  572.         hist_info *hist;
  573.         int        filter;
  574.         int        colours;
  575.         int        target;
  576.         int        i;
  577.  
  578.         /* check for non paletted / too small palette output image */
  579.  
  580.         if(out->bpp>8 || out->bpp<4) return;
  581.  
  582.         /* build histogram of colour use counts */
  583.  
  584.         hist = build_histogram(in);
  585.         
  586. #ifdef HASH_STAT
  587.         fprintf(stderr,"Hash used   : %-7d %3d%%\n",hist->hash_used,
  588.                                                     hist->hash_used*
  589.                                                     100/HASH_SIZE);
  590.         fprintf(stderr,"Hash hits   : %-7d %3d%%\n",hist->hash_hits,
  591.                                                     hist->hash_hits*
  592.                                                     100/(in->X*in->Y));
  593.         fprintf(stderr,"Hash misses : %-7d %3d%%\n",hist->hash_miss,
  594.                                                     hist->hash_miss*
  595.                                                     100/(in->X*in->Y));
  596.         fprintf(stderr,"Hash chain  : %-7d\n",      hist->hash_chain);
  597. #endif
  598. #ifdef COLOUR_STAT
  599.         fprintf(stderr,"Colours used: %d\n",hist->colours);
  600.         fprintf(stderr,"used > 1    : %d\n",hist->more1);
  601.         fprintf(stderr,"used > 10   : %d\n",hist->more10);
  602.         fprintf(stderr,"used > 100  : %d\n",hist->more100);
  603.         fprintf(stderr,"used > %.2f%%: %-5d (%d pixels)\n",
  604.                                             100.0/(float)FILTER_FRAC,
  605.                                             hist->more_frac,
  606.                                             hist->fraction);
  607. #endif
  608.  
  609.         filter = calc_filter(hist, out->cols);
  610.         filter_histogram(hist, filter);
  611.  
  612. #ifdef COLOUR_STAT
  613.         fprintf(stderr,"Filer chosen: %d\n",filter);
  614.         fprintf(stderr,"Table size  : %d\n",table_size);
  615. #endif
  616.  
  617.         /*
  618.          * for each colour in the table find the 
  619.          * closest color in the rest of the table
  620.          */
  621.  
  622.         make_closests();
  623.  
  624.         progress_start("Optimizing  :");
  625.  
  626.         colours = table_size;
  627.  
  628.         while(colours > out->cols)
  629.         {
  630.                 target = find_closest();
  631.                 eliminate(target);
  632.                 update_closests(target);
  633.                 colours--;
  634.                 progress(table_size - colours, table_size - out->cols);
  635.         }
  636.  
  637.         progress_finish();
  638.  
  639.         /*
  640.          * copy optimization table to destination palette
  641.          * and remove table storage
  642.          */
  643.  
  644.         colours = 0;
  645.  
  646.         for(i=0; i<table_size; i++)
  647.         {
  648.                 if(table[i] != 0)
  649.                 {
  650.                         out->palette[colours++] = table[i]->value;
  651.  
  652.                         free((void*)table[i]);
  653.                 }
  654.         }
  655.         free((void*)table);
  656. }
  657.  
  658.